package teaching;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: fzykd
 * Date: 2022-11-13
 * Time: 18:55
 */

//基数排序
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = new int[80000000];
        //产生随机数

        //计算内存
        //80000000 * 11(这样的数组) * 4(一个int4个字节) /1024(k)/1024(兆)/1024(G) ≈ 3.3G

        for (int i = 0; i < 80000000; i++) {
            arr[i] = (int) (Math.random()*800000); //生成[0-800000)数
        }

        Date data1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1 = simpleDateFormat.format(data1);
        System.out.println("排序前的时间输出=" + date1);

        //运行冒泡排序
        radixSort(arr);

        Date data2 = new Date();
        String date2 = simpleDateFormat.format(data2);
        System.out.println("排序后的时间输出=" + date2);
    }


    public static void radixSort(int[] arr){
        //先得到数组中最大的位数
        int max = arr[0]; //假设第一个数是一个最大数
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max){
                max = arr[i];
            }
        }
        //得到最大数 是几位 决定了后面排序有几轮
        int maxLength = (max + "").length();

        //第一轮排序 针对每个元素的各位排数处理

        //首先定义一个二维数组来表示10个桶 每个桶就是一个一维数组
        //二维数组包含了10个一维数组 2.为了防止放入数组的时候越界 只能极端的定位arr.length
        //基数排序 是使用空间换时间的典型算法
        int[][] bucket = new int[10][arr.length];

        //为了记录每个桶中存放了多少个实际数据 定义一个一维数组 来记录各个桶中存放了多少数据
        int[] bucketSize = new int[10];

        for (int i = 0,n=1; i < maxLength; i++,n*=10) {
            //放数据
            for (int j = 0; j < arr.length; j++) {
                //取出每个元素的个位
                int digitOfElement = arr[j] / n % 10;
                //放入到对应的桶中
                bucket[digitOfElement][bucketSize[digitOfElement]] = arr[j];
                bucketSize[digitOfElement]++;
            }
            //按照这个桶的顺序 (一维数组的下标一次读取数据，放入到原来的数组当中)
            int index = 0;
            //遍历每一个桶
            for (int k = 0; k < bucketSize.length; k++) {
                //如果桶里有数据 才放入元数据
                if (bucketSize[k] != 0){
                    //循环第k个桶 即第k个一维数组
                    for (int l = 0; l < bucketSize[k]; l++) {
                        //取出方法到原先的arr
                        arr[index] = bucket[k][l];
                        index++;
                    }
                }
                bucketSize[k] = 0;

            }
           // System.out.println("第一轮" + Arrays.toString(arr));
        }


    }



    public static void radixSort1(int[] arr){
        //第一轮排序 针对每个元素的各位排数处理

        //首先定义一个二维数组来表示10个桶 每个桶就是一个一维数组
        //二维数组包含了10个一维数组 2.为了防止放入数组的时候越界 只能极端的定位arr.length
        //基数排序 是使用空间换时间的典型算法
        int[][] bucket = new int[10][arr.length];

        //为了记录每个桶中存放了多少个实际数据 定义一个一维数组 来记录各个桶中存放了多少数据
        int[] bucketSize = new int[10];
        
        //放数据
        for (int j = 0; j < arr.length; j++) {
            //取出每个元素的个位
            int digitOfElement = arr[j] % 10;
            //放入到对应的桶中
            bucket[digitOfElement][bucketSize[digitOfElement]] = arr[j];
            bucketSize[digitOfElement]++;
        }


        //第一轮
        //按照这个桶的顺序 (一维数组的下标一次读取数据，放入到原来的数组当中)
        int index = 0;
        //遍历每一个桶
        for (int k = 0; k < bucketSize.length; k++) {
            //如果桶里有数据 才放入元数据
            if (bucketSize[k] != 0){
                //循环第k个桶 即第k个一维数组
                for (int l = 0; l < bucketSize[k]; l++) {
                    //取出方法到原先的arr
                    arr[index] = bucket[k][l];
                    index++;
                }
            }
            //第一轮之后 将桶数据清零
            bucketSize[k] = 0;
        }
        System.out.println("第一轮" + Arrays.toString(arr));

        //第二轮
        //放数据
        for (int j = 0; j < arr.length; j++) {
            //取出每个元素的个位
            int digitOfElement = arr[j] /10 % 10;
            //放入到对应的桶中
            bucket[digitOfElement][bucketSize[digitOfElement]] = arr[j];
            bucketSize[digitOfElement]++;
        }
        index = 0;
        //按照这个桶的顺序 (一维数组的下标一次读取数据，放入到原来的数组当中)
        //遍历每一个桶
        for (int k = 0; k < bucketSize.length; k++) {
            //如果桶里有数据 才放入元数据
            if (bucketSize[k] != 0){
                //循环第k个桶 即第k个一维数组
                for (int l = 0; l < bucketSize[k]; l++) {
                    //取出方法到原先的arr
                    arr[index] = bucket[k][l];
                    index++;
                }
            }
            bucketSize[k] = 0;
        }
        System.out.println("第二轮" + Arrays.toString(arr));


        //第三轮
        //放数据
        for (int j = 0; j < arr.length; j++) {
            //取出每个元素的个位
            int digitOfElement = arr[j] /10/10 % 10;
            //放入到对应的桶中
            bucket[digitOfElement][bucketSize[digitOfElement]] = arr[j];
            bucketSize[digitOfElement]++;
        }

        index = 0;
        //按照这个桶的顺序 (一维数组的下标一次读取数据，放入到原来的数组当中)
        //遍历每一个桶
        for (int k = 0; k < bucketSize.length; k++) {
            //如果桶里有数据 才放入元数据
            if (bucketSize[k] != 0){
                //循环第k个桶 即第k个一维数组
                for (int l = 0; l < bucketSize[k]; l++) {
                    //取出方法到原先的arr
                    arr[index] = bucket[k][l];
                    index++;
                }
            }
            bucketSize[k] = 0;
        }
        System.out.println("第三轮" + Arrays.toString(arr));
    }
}
